package lc;

import java.util.Arrays;

import org.junit.Test;

public class Ex31 {
    class Solution {
        public void nextPermutation(int[] nums) {
            int n = nums.length;
            //1,2,3,1,0
            for (int i = n - 2; i >= 0; i--) {
                if (nums[i] < nums[i + 1]) {
                    int tmp = nums[i];
                    int j = n - 1;
                    while (nums[j] < tmp) {
                        j--;
                    }
                    for (int k = i; k < j; k++) {
                        nums[k] = nums[k + 1];
                    }
                    nums[j] = tmp;
                    reverse(nums, i + 1);
                    return;
                }
            }
            reverse(nums, 0);
        }
    
        public void reverse(int[] nums, int i) {
            //将i以后的部分左右交换
            int n = nums.length;
            for (int j = 0; j < (n - i + 1) / 2; j++) {
                int tmp = nums[n - j - 1];
                nums[n - j - 1] = nums[i + j];
                nums[i + j] = tmp;
            }
        }
    }

    @Test
    public void test() {
        Solution s = new Solution();
        int[] nums = new int[]{1,2,3};
        s.nextPermutation(nums);
        System.out.println(Arrays.toString(nums));
    }
}
